package com.it.od.od2024;

import java.util.ArrayList;
import java.util.List;

/**
 * @author: liminghui
 * @date: 2024/1/18 23:53
 * @version: 1.0
 * @description: 全排列方案 dfs 深搜+递归+标记数组
 */
public class Main4 {
    public static void main(String[] args) {
        String[] words = new String[]{"a", "b", "c"};
        List<List<String>> result = new ArrayList<>();
        List<String> candidate = new ArrayList<>();
        boolean[] visited = new boolean[words.length];
        dfs2(words, visited, candidate, result);
        System.out.println(result);
    }

    // 方法一：深搜，dfs
    public static void dfs(String[] words, List<String> candidate, List<List<String>> result) {
        List<String> temp = new ArrayList<>(candidate);
        if (temp.size() == words.length) {
            result.add(temp);
            return;
        }
        for (String word : words) {
            if (temp.contains(word)) {
                continue;
            }
            temp.add(word);
            dfs(words, temp, result);
            temp.remove(word);
        }
    }

    // 方法二：深搜dfs+標記數組+递归
    public static void dfs2(String[] words, boolean[] visited, List<String> candidate, List<List<String>> result) {
        List<String> temp = new ArrayList<>(candidate);
        if (temp.size() == words.length) {
            result.add(temp);
            return;
        }
        for (int i = 0; i < words.length; i++) {
            if (visited[i]) {
                continue;
            }
            temp.add(words[i]);
            visited[i] = true;
            dfs2(words, visited, temp, result);
            visited[i] = false;
            temp.remove(words[i]);
        }
    }
}
